The technical field relates to an apparatus and a method for color halftoning, and in particular, a dither matrix design for color halftoning that uses dot clusters whose centers are distributed homogeneously and isotropically.
The purpose of digital halftoning is to render a continuous tone image using an output device with a limited pallet, or set of available colors. In practice there are two halftoning techniques, point processing and neighborhood processing. In point processing, pixels are halftoned in isolation of one another, meaning that the pixels need not be processed in any particular order, thus requiring less processing capacity and less memory. In neighborhood processing, each pixel is quantized based on the pixel itself in addition to neighboring pixels. As a result, pixels may have to be processed in a particular order, requiring greater computational capability and perhaps utilizing an excessive amount of memory. As the present application focuses on point processing techniques, point processing will be described in further detail.
In a majority of point processing techniques, halftoning is implemented by screening, which is implemented using dither matrices. In screening, an array of thresholds, which is tiled across the image, is required, the array having finite dimensions of height and width. Each pixel is quantized strictly based on a comparison between the pixel value and the corresponding threshold value. Therefore any halftoning process using the dither matrix relies heavily on the dither matrix itself since the dither matrix has such a heavy bearing on the appearance of the output image.
In the vast majority of the literature concerning halftoning using dither matrices, there are two types of screening or halftoning processes in use. The first is clustered dot halftoning, which is also known as amplitude modulation halftoning. In clustered dot halftoning, the halftone dither matrix encourages formation of dot clusters arranged on a rectangular lattice, which may be rotated. The darkness or lightness of an image is dependent on the size of the fixed dots in the image. Clustered dot halftoning is ideal for unstable printing devices, e.g. earlier generation laser printers. When printed in isolation, dots from such early generation laser printers may not develop predictably, and may appear diffuse, very soft, very hard to see, or sometimes not even there at all. However, when printed in groups, dot clusters are consistent in size and easy to see. As a result, clustered dot printing, which arranges dots so that they are clustered together, is more reliable for unstable laser printers.
There are two problems associated with clustered dot halftoning. First, the clustered dot halftoning technique can lead to the creation of moirxc3xa9 artifacts. The moirxc3xa9 effect is the interference pattern created by superimposing two or more regular patterns. The moirxc3xa9 effect typically comes about when a previously rendered image is recreated, i.e. when printing an image that was first printed, then scanned into a computer. The moirxc3xa9 effect occurs because the previously rendered image has already been sampled. The previously rendered image has a periodicity from the sampling rate of the prior printing. This periodicity is propagated to the current printing and the discrepancies between the two periodicities result in unsightly artifacts in the final rendering. The second problem associated with clustered dot halftoning is that the level of detail that can be rendered is reduced because of the clustered nature of the dots.
The second type of screening technique is dispersed dot halftoning. In dispersed dot halftoning, which is also known as frequency modulation (FM) halftoning, the darkness or lightness of a tone is dependent of the density of the dot distribution. For instance, darker tones are caused by having a higher density of dots in a particular area, but not by clustering the dots. Dispersed dot halftoning allows for finer detail rendition. By not clustering the smallest indivisible printed dots, dispersed dot halftoning maximizes the spatial resolution of printed images relative to the resolution of the printer. Furthermore, dispersed dot halftoning is more resistant to the moirxc3xa9 effect. Dispersed dot halftoning avoids the moirxc3xa9 effect because the process arranges dots in a random fashion. Dispersed dot halftoning avoids imparting periodicity to the rendered image and thereby avoid creating moirxc3xa9 effect artifacts.
One problem associated with dispersed dot halftoning is that the technique is not appropriate for unstable printers, e.g. earlier generation laser printers. The dispersed nature of the dot pattern means that if a dot in a particular location is not visibly printed, there are no nearby dots to compensate for the lack of a visible dot in that location.
What is needed is a design for matrices for color halftoning which is a cross between traditional clustered dot and dispersed dot screening and allows the formation of dot clusters whose centers are arranged homogeneously and isotropically, thus allowing for a smoother and more even appearing image and finer detail rendering while being resistant to the moirxc3xa9 effect and providing more reliable printing for unstable printers.
A method for dither matrix design for color halftoning using dispersed dot clusters, comprises placing dot seeds in an array, arranging the dot seeds such that the resulting pattern is homogeneous and isotropic to minimize the results of the moirxc3xa9 effect, arranging labels on the dot seeds corresponding to the different colors to be printed such that each dot seed of a particular color is well dispersed from other dot seeds of the same color, growing dot clusters around the dot seeds of each color after having separated the seeds of each color into its own separate array, and finally outputting the results, a collection of screens corresponding to each of the colors, to a file. In one embodiment, three color labels are assigned. In a preferred embodiment, the three color labels are cyan, magenta, and yellow. In an alternative embodiment, four color labels are assigned. In an alternative preferred embodiment, the four color labels are cyan, magenta, yellow, and black. In a preferred embodiment, the method further comprises the step of placing additional dot seeds labeled with an additional color into spaces between the dot seeds that have been arranged with color labels. In one embodiment, the additional color is yellow.
An apparatus for implementing the method for dither matrix design for color halftoning using dispersed dot clusters, comprises a module for placing dot seeds in an array, a module for arranging the dot seeds such that the resulting pattern is homogeneous and isotropic to minimize the results of the moirxc3xa9 effect, a module for arranging labels on the dot seeds for the different colors to be printed such that each dot seed of a particular color is well dispersed from other dot seeds of the same color, a module for growing dot clusters around the dot seeds after having separated the seeds of each color into its own separate array, and a module for outputting the results, a collection of screens corresponding to each of the colors, to a file. In one embodiment, three color labels are assigned. In a preferred embodiment, the three color labels are cyan, magenta, and yellow. In an alternative embodiment, four color labels are assigned. In an alternative preferred embodiment, the four color labels are cyan, magenta, yellow, and black. In a preferred embodiment, the method further comprises the step of placing additional dot seeds labeled with an additional color into spaces between the dot seeds that have been arranged with color labels. In one embodiment, the additional color is yellow.
In a preferred embodiment, the size of the array as well as the number of dot seeds that will be in the array are predetermined. Also, in a preferred embodiment, dot clusters are grown around each dot seed in a spiral pattern.
As a result of the dispersed dot clusters method, each screen taken alone would substantially have the property that using the screen creates an image with dispersed clusters of printed dots. However, a set of screens configured using the dispersed dot clusters method would have the additional property that using them together would allow color images to consist of smoother textures, having less color fluctuation.
The apparatus and method for dither matrix design for color halftoning using dispersed dot clusters may be implemented on a machine, which comprises a memory containing the instructions for implementing the apparatus and method for dither matrix design for color halftoning using dispersed dot clusters, a processor for accessing the memory and implementing the instructions, and an output device controlled by the processor for displaying an output resulting from the execution of the instructions. In a preferred embodiment, the machine is a computer connected to a printer output device.